package algorithm.sort;

import org.junit.Before;
import org.junit.Test;

import java.util.Arrays;

/**
 * 快速排序
 * 在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。
 * 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。
 */
public class QuickSort {

    private final int[] arr = new int[15];

    @Before
    public void init() {
        for (int i = 0, j = arr.length; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * j);
        }
    }

    @Test
    public void quickSort() {
        System.out.println("排序前:" + Arrays.toString(arr));
        int len = arr.length;
        sort(arr, 0, len - 1);
        System.out.println("排序后:" + Arrays.toString(arr));
    }

    public void sort(int[] array, int left, int right) {
        if (left > right) {
            return;
        }
        // base中存放基准数
        int base = array[left];
        int i = left, j = right;
        while (i != j) {
            // 顺序很重要，先从右边开始往左找，直到找到比base值小的数
            while (array[j] >= base && i < j) {
                j--;
            }

            // 再从左往右边找，直到找到比base值大的数
            while (array[i] <= base && i < j) {
                i++;
            }

            // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置
            if (i < j) {
                swap(i, j);
            }
        }

        // 将基准数放到中间的位置（基准数归位）
        array[left] = array[i];
        array[i] = base;

        // 递归，继续向基准的左右两边执行和上面同样的操作
        // i的索引处为上面已确定好的基准值的位置，无需再处理
        sort(array, left, i - 1);
        sort(array, i + 1, right);
    }


    private void swap(int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }


}
